/**
 * 
 */
package leetCode;

/**
 * 含有所有最深的叶节点的子树，思路：向上返回深度，如果相等，则都上传当前节点，否则，上传深的子节点及其深度
 * 
 * @author zhong
 *
 */
public class SmallestSubtreewithalltheDeepestNodes {
	public class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;

		TreeNode(int x) {
			val = x;
		}
	}

	public TreeNode subtreeWithAllDeepest(TreeNode root) {
		return helper(root, 1, new int[1]);
	}

	private TreeNode helper(TreeNode root, int height, int[] depth) {
		if (root == null) {
			return null;
		}
		if (root.left == null && root.right == null) {
			depth[0] = height + 1;
			return root;
		}
		int[] lD = new int[1];
		int[] rD = new int[1];
		TreeNode lNode = helper(root.left, height + 1, lD);
		TreeNode rNode = helper(root.right, height + 1, rD);

		if (lD[0] == rD[0]) {
			depth[0] = lD[0] + 1;
			return root;
		} else if (lD[0] > rD[0]) {
			depth[0] = lD[0] + 1;
			return lNode;
		} else {
			depth[0] = rD[0] + 1;
			return rNode;
		}

	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		System.out.println(new SmallestSubtreewithalltheDeepestNodes().subtreeWithAllDeepest(null));

	}

}
